package com.muchfish.algorithm.queue;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 柱状图中最大的矩形
 * 给定非负整数数组 heights ，数组中的数字用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
 * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
 * <p>
 * 示例1：
 * <p>
 * <img src="https://assets.leetcode.com/uploads/2021/01/04/histogram.jpg">
 * <p>
 * 输入：heights = [2,1,5,6,2,3]
 * 输出：10
 * 解释：最大的矩形为图中红色区域，面积为 10
 */
public class LargestRectangleArea {
    /**
     * 暴力法
     * 找以每个元素为高度的最大矩形的左右两个下标的方式是从当前位置向两边扩散
     * 注意边界和索引边界
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        //暴力破解
        int max = 0;
        for (int i = 0; i < heights.length; i++) {
            //用两个指针分别向左右扩散,寻找以当前heights[i]为高度的最大矩形的左右两个下标，
            int left = i;
            int right = i;
            while (left > 0) {
                left--;//向左边扩散
                if (heights[left] < heights[i]) {
                    left++;//最左边的下标
                    break;
                }
            }
            while (right < heights.length - 1) {
                right++;//向右边扩散
                if (heights[right] < heights[i]) {
                    right--;
                    break;
                }
            }
            int tempArea = (right - left + 1) * heights[i];
            max = Math.max(max, tempArea);
        }
        return max;
    }

    /**
     * 单调栈+哨兵
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea2(int[] heights) {
        //特殊判断
        if (heights == null) {
            return 0;
        } //构造一个新数组，安排好哨兵
        int[] h = new int[heights.length + 2];
        h[0] = -1;
        h[h.length - 1] = -1;
        System.arraycopy(heights, 0, h, 1, heights.length);
        Deque<Integer> stack = new ArrayDeque();
        //遍历前将左侧哨兵入栈
        stack.push(0);
        //定义最大面积
        int max = 0;
        for (int i = 1; i < h.length; i++) {
            while (h[i] < h[stack.peek()]) {
                //栈顶元素对应的高度
                int height = h[stack.pop()];
                max = Math.max(max, (i - 1 - stack.peek()) * height);
            }
            stack.push(i);
        }
        return max;
    }
}
